package com.leetcode.回溯;

import java.util.ArrayList;
import java.util.List;

public class lc_17 {
    // 用一个数组，在每个号码对应的索引位置存储对应的 字母字符串
    String[] letter_map = {
            " ", "*", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"
    };

    public List<String> letterCombinations(String digits) {
        // 边界情况判断
        if (digits == null || digits.length() == 0) {
            return new ArrayList<>();
        }

        List<String> ans = new ArrayList<>(); //用来保存最终返回的字符串集合
        StringBuilder str = new StringBuilder();  // 用来保存每次拼接的结果
        backTrack(digits, ans, 0, str);   // 递归函数调用
        return ans; // 返回结果
    }

    //  递归函数
    //  参数依次为 输入的数字字符串、 最终结果、 初始字符串索引、存放每次拼接结果的字符串
    public void backTrack(String digits, List<String> ans, int index, StringBuilder str) {
        // 判断是否到递归尽头：即是否索引位置到了最后
        // 若到底，则把拼好的字符串 加入到结果集合中，并返回到上一层递归
        if (index == digits.length()) {
            ans.add(str.toString());
            return;
        }

        // 取出数字对应的字母字符串
        String num = letter_map[(digits.charAt(index) - '0')];  // 这里本来写成了（int）（(digits.charAt(index)），＊＊＊了，因为char强转为int会变成ascii码值

        // 得到字母的个数
        int numLetters = num.length();

        // 循环拼接字符串的过程
        /*
         * 例：输入 “23”，则对应“abc” “def”这样两个字符串
         * 以上案例详解该循环中的递归：
         * 1.把“abc”中的"a"取出，append进str中
         * 2.递归调用backTrack，但传入索引index+1，即index为1的backTrack；进入下一轮，即“def”的拼接伦次
         * 3.进入第二层的backTrack后，先把"d"append进str中，进入第三层index为2的backTrack
         * 4.此时index == digits.length()，意味着递归到达尽头，把str中的"ad"add进结果集合ans
         * 5.回到第二层backTrack，先把"ad"中的"d"去除，进入下一层for循环，同步骤2-4，依次把"ae"、"af"加入结果结合ans
         * 6.结束第二层的循环后，回到第一层循环，此时str为"a"（上一步执行了"ae"去除e)
         * 7.去除str中的"a",通过第一层的for循环依次执行"b"、"c"的伦次，同步骤1-6
         * 8.结束递归
         */
        for (int i = 0; i < numLetters; i++) {
            str.append(num.charAt(i)); //
            backTrack(digits, ans, index + 1, str);
            str.deleteCharAt(str.length() - 1);
        }
    }
    public static void main(String[] args) {
        lc_17 solution = new lc_17();
        String digits = "23"; // 测试输入，可以更改为其他数字组合
        List<String> result = solution.letterCombinations(digits);
        System.out.println("输入数字: " + digits);
        System.out.println("可能的字母组合: " + result);
    }
}
